Programming Interviews Exposed by John Mongan & Eric Giguère & Noah Kindler

Author:John Mongan & Eric Giguère & Noah Kindler
Language: eng
Format: epub
Publisher: John Wiley & Sons, Inc.
Published: 2012-11-09T16:00:00+00:00

Multi-Key Sort

PROBLEM You have an array of objects, each of which represents an employee:

public class Employee { public String extension; public String givenname; public String surname; }

Using a standard library sorting routine, sort the array so it is ordered alphabetically by surname and then by given name as in a company phone book.

To sort the data using a routine from the standard library, you need a comparator: a function that compares two objects. A comparator returns a negative value if the first object is “less than” the second object; zero if the two objects have equal keys; or a positive value if the first object is “greater than” the second.

For this problem, there are two components of the key: The surname and the given name, so the comparator needs to use both of these values. You must order first by surname and then by given name, so the comparator should start by comparing the surnames and then resolve ties by comparing the given names.

In Java, comparators implement the java.util.Comparator interface:

import java.util.Comparator; // A comparator for Employee instances. public class EmployeeNameComparator implements Comparator<Employee> { public int compare( Employee e1, Employee e2 ){ // Compare surnames int ret = e1.surname.compareToIgnoreCase( e2.surname ); if( ret == 0 ){ //Compare givennames if surnames are the same ret = e1.givenname.compareToIgnoreCase( e2.givenname ); } return ret; } }

Now it’s just a matter of invoking the Arrays.sort method with the array and the comparator:

public void sortEmployees( Employee[] employees ){ Arrays.sort( employees, new EmployeeNameComparator() ); }

The approach shown here of using a comparator that considers both parts of the key in a single sort is the most efficient approach, but there is another alternative. If the sort routine you use is stable (the modified merge sort used by Arrays.sort is), you can achieve the same result by calling the sort routine twice and sorting on one part of the key at a time. For this problem, you would first sort by given name and then make a second call to sort by surname. During the second sort, by the definition of a stable sort, employees with the same surname would retain their relative ordering based on given name, established by the first sort.

Download

Copyright Disclaimer:
This site does not store any files on its server. We only index and link to content provided by other sites. Please contact the content providers to delete copyright contents if any and email us, we'll remove relevant links or contents immediately.